﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using FCA.Dto;
using FCA.Helper;

namespace FCA.Algorithm {
    public class CLICL {
        public Lattice L { get; set; }
        public IndexTable FirstNodes { get; set; }

        public CLICL() {
            L = new Lattice();
            FirstNodes = new IndexTable();
        }

        public void InitLattice(int tid, List<int> t) {
            //the first itemset            
            Concept root = new Concept();
            root.ID = 0;
            L.AddConceptWithID(root);
            L.RootNodeID = 0;
            root.Tids.AddUnique(1);


            Concept lastNode = new Concept();
            lastNode.ID = 0;
            lastNode.Items = t;
            L.AddConcept(lastNode);
            L.LastNodeID = 1;

            Concept firstNode = new Concept();
            firstNode.ID = 1;
            firstNode.Items = t;
            firstNode.Tids.AddUnique(1);
            L.AddConcept(firstNode);

            root.AddChild(firstNode);
            firstNode.AddChild(lastNode);

            foreach (int item in t) {
                FirstNodes.AddIndex(item, 2);
            }
        }
        ////Build Base lattice

        ////Delete transaction

        /// <summary>
        /// Add transaction to the current Lattice L 
        /// </summary>
        /// <param name="tid">transaction id</param>
        /// <param name="t">item set of the transaction to insert</param>        
        public void AddTransaction(int tid, List<int> t) {
            //update lastNode
            L.Concepts[L.LastNodeID].Items = L.Concepts[L.LastNodeID].Items.UnionWith(t);
            //update root node
            L.Concepts[L.RootNodeID].Tids.AddUnique(tid);
            Concept temp = ItemSetIsExistedInLattice(t);
            if (temp != null) {
                temp.Tids.AddUnique(tid);
                //Console.WriteLine("add {0} to concept {1}", tid, tid);
                return;
            }

            //create a new Node N with In = t
            AddTransaction(new List<int>() { tid }, t);

        }

        public void AddTransaction(List<int> tids, List<int> items) {
            Concept n = new Concept();
            n.Items = items;
            foreach (int tid in tids) {
                n.Tids.AddUnique(tid);
            }
            List<int> checkedItemIndex = new List<int>();

            bool isAdded = false;
            //for all item i in t in L do
            foreach (int i in items) {

                int index = FirstNodes.GetFirstNode(i);
                if (index == -1) {
                    if (isAdded) {
                        FirstNodes.AddIndex(i, n.ID);
                    }
                    continue;
                }
                if (checkedItemIndex.Contains(index)) {
                    continue;
                }
                checkedItemIndex.Add(index);
                Concept fi = L.Concepts[index];
                //if Fi is ancestor of N then (this is the common case)
                if (fi.Items.IsAncestorOf(n.Items)) {
                    //find child and parents of N among the descendants of fi
                    Case1(n, fi, ref isAdded, tids.Count);
                } else if (fi.Items.IsDescendantOf(n.Items)) {
                    //if Fi is descendant of N 
                    //child of N is Fi and parents of N are among the ancestors of fi
                    Case2(n, fi, i, ref isAdded);

                } else {
                    Case3(n, fi, i, ref isAdded, tids.Count);
                }
            }
            if (!isAdded) {
                L.AddConcept(n);
                n.AddParent(L.Concepts[L.RootNodeID]);
            }

            if (n.ChildrenID.Count == 0) {
                n.AddChild(L.Concepts[L.LastNodeID]);
            }
            foreach (int item in items) {
                if (!FirstNodes.ContainsKey(item)) {
                    FirstNodes.AddIndex(item, n.ID);
                }
            }
        }

        #region Case 3
        private void Case3(Concept n, Concept fi, int i, ref  bool isAdded, int tidCount) {
            //if common parent X of Fi and N exist in L then
            //  parent of N is X and child of N is among descendants of fi
            //else
            //  create a new node X where Ix = Ifi and In
            //  parent of N is X and child of N is among descendants of Fi
            //  children of X are fi and some ancestor of N
            //  parents of X are among the ancestors of fi
            //  if X is neither ancestor nor descendant of node Y thuoc L and Ix and Iy khac rong
            //  then
            //      create a new node U such that Iu = Iy and Ix
            //      find child and parents of node U
            //  end if
            //end if

            //Case 3: Fi is neither ancestor nor descendent of N.  (Ifi not in In, Ifi not cover In, Ifi /\ In <> null)
            //In this case, common parent of Fi and N with closed itemset as X = Ifi /\ In may exists in L or it may not exist
            if (!isAdded) {
                isAdded = true;
                L.AddConcept(n);
            }
            Concept x = new Concept();
            x.Items = fi.Items.IntersectWith(n.Items);

            Concept t = ItemSetIsExistedInLattice(x.Items);
            List<int> tids = fi.Tids.UnionWith(n.Tids);
            //Case 3.1: Ifi /\ In exists as closed itemset of a node X in L
            //If such a node X existed in L then 
            //  X is parent of N. 
            //  Child of N is among the descendants of Fi. We check all the descendants of Fi till we find a node
            //      whose closed itemset is minimal superset of closed itemset of N, that node becomes the child of N
            if (t != null) {
                t.Tids = tids;

                Case3_1(n, fi, t, i, tidCount);
            } else {
                //Case 3.2: Ifi /\ In does not exists as closed itemset of a node X in L
                //A new node X is created with Ix = Ifi /\ In and added to L. 
                //  X becomes the parent of N 
                //  and child of N is among the descendants of Fi.
                //      We check all the descendants of Fi till we get a node
                //          those closed itemset is minimal superset of closed itemset of N, that node becomes the child of N.
                x.Tids = tids;
                Case3_2_1_FindParentAndChildOfXInDescendantsOfFi(n, fi, x, tidCount);

                //Next step is to find the child and parents of X.
                //  Parents of X are among the ancestors of Fi
                //      We check all the ancestors of Fi. If we get a node Y such that 
                //          closed itemset of Y is superset of X 
                //          and closed itemset of one of the parent Z of Y is subset of X
                //          then Z becomes the parent of X
                //          and Y is child of X
                //  If we find an ancestor Y of Fi such that Y is neither ancestor nor descendent of X, then
                //      a new node U is created with Iu = Iy /\ Ix.
                //      Then we repeat the process to find child and parents of node U 
                x.AddChild(fi);
                FirstNodes.UpdateIndexIfExisted(i, x.ID, fi.ID);
                List<int> checkedConceptIds = new List<int>();
                List<int> notParentIds = new List<int>();
                List<int> notChildIds = new List<int>();
                bool isFind = false;

                Case3_2_2_FindChildAndParentOfXInAncestorFi(x, fi, checkedConceptIds, notParentIds, notChildIds, tidCount, ref isFind);
                //Case3_2_2_Wrong(x, fi, fi, i);
            }
        }

        private void Case3_2_2_FindChildAndParentOfXInAncestorFi(Concept n, Concept currentNode, List<int> checkedConceptIds, List<int> notParentIds, List<int> notChildIds, int tidCount, ref bool isFind) {
            if (isFind || checkedConceptIds.Contains(currentNode.ID)) { return; }
            foreach (int parentID in currentNode.GetParentID()) {
                if (checkedConceptIds.Contains(parentID) || n.ID == parentID) { continue; }
                Concept parent = L.Concepts[parentID];
                bool isNotInChild = notChildIds.Contains(parentID);
                if (isNotInChild) {
                    notChildIds = notChildIds.UnionWith(parent.ChildrenID);
                }
                bool isSuperSet = parent.Items.IsSuperSetOf(n.Items);

                if (!isNotInChild && isSuperSet) {
                    //all parents of parent isn't superset of x => add parent as x parent
                    bool noParentOfParentIsSuperSet = true;
                    bool needLoop = true;


                    foreach (int parentOfParentID in parent.GetParentID()) {
                        if (n.ID == parentOfParentID) { continue; }
                        Concept parentOfParent = L.Concepts[parentOfParentID];
                        if (notChildIds.Contains(parentOfParentID)) {
                            notChildIds = notChildIds.UnionWith(parentOfParent.ChildrenID);
                            continue;
                        }

                        if (parentOfParent.Items.IsSuperSetOf(n.Items)) {
                            noParentOfParentIsSuperSet = false;
                            notChildIds.Add(parentID);
                            break;
                        } else {
                            bool isNotInParent1 = notParentIds.Contains(parentOfParentID);
                            if (isNotInParent1) {
                                notParentIds = notParentIds.UnionWith(parentOfParent.ChildrenID);
                            }
                            if (!isNotInParent1 && parentOfParent.Items.IsSubSetOf(n.Items)) {
                                //remove connection between child and childOfChild
                                parent.RemoveParent(parentOfParent);
                                parent.AddParent(n);
                                n.AddParent(parentOfParent);
                                checkedConceptIds.AddUnique(parentOfParent.ID);
                                checkedConceptIds.AddUnique(parent.ID);
                                //break;
                            }
                        }

                    }
                    if (noParentOfParentIsSuperSet) {
                        //=> parent is superSet of x
                        parent.AddParent(n);
                        notChildIds = notChildIds.UnionWith(parent.ChildrenID);
                        notChildIds.AddUnique(parentID);

                        notParentIds = notParentIds.UnionWith(parent.ChildrenID);
                        notParentIds.AddUnique(parentID);

                        checkedConceptIds.AddUnique(parent.ID);
                    }
                    if (needLoop) {
                        Case3_2_2_FindChildAndParentOfXInAncestorFi(n, parent, checkedConceptIds, notParentIds, notChildIds, tidCount, ref isFind);
                    }
                }

                bool isSubSet = parent.Items.IsSubSetOf(n.Items);
                bool isInNotParent = notParentIds.Contains(parentID);
                if (isInNotParent) {
                    notParentIds = notParentIds.UnionWith(parent.ParentID);
                }
                if (!isInNotParent && isSubSet) {

                    n.AddParent(parent);
                    notChildIds = notChildIds.UnionWith(parent.ParentID);
                    notChildIds.AddUnique(parentID);

                    notParentIds = notParentIds.UnionWith(parent.ParentID);
                    notParentIds.AddUnique(parentID);
                    checkedConceptIds.AddUnique(parentID);

                    foreach (int childOfParentID in parent.GetChildrentID()) {
                        if (n.ID == childOfParentID) { continue; }
                        Concept childOfParent = L.Concepts[childOfParentID];
                        bool isNotInChild1 = notChildIds.Contains(childOfParentID);
                        if (isNotInChild1) {
                            notChildIds = notChildIds.UnionWith(childOfParent.ParentID);
                        }
                        if (!isNotInChild1 && childOfParent.Items.IsSuperSetOf(n.Items)) {
                            childOfParent.RemoveParent(parent);
                            childOfParent.AddParent(n);
                            n.AddParent(parent);
                            checkedConceptIds.AddUnique(parentID);
                            checkedConceptIds.AddUnique(childOfParentID);
                        }
                    }
                    if (tidCount == 1) { isFind = true; return; }
                }
                if (!isSuperSet && !isSubSet) {
                    Concept newNode = new Concept();
                    newNode.Items = n.Items.IntersectWith(parent.Items);
                    Concept existedNode = ItemSetIsExistedInLattice(newNode.Items);
                    if (newNode.Items.Count > 0 && existedNode == null) {
                        AddTransaction(n.Tids.UnionWith(parent.Tids), newNode.Items);
                    } else if (existedNode != null) {
                        n.AddParent(existedNode);
                        checkedConceptIds.Add(existedNode.ID);
                    }
                }


            }

        }

        private void Case3_2_1_FindParentAndChildOfXInDescendantsOfFi(Concept n, Concept fi, Concept x, int tidCount) {
            //Case 3.2: Ifi /\ In does not exists as closed itemset of a node X in L
            //A new node X is created with Ix = Ifi /\ In and added to L. 
            //  X becomes the parent of N 
            //  and child of N is among the descendants of Fi.
            //      We check all the descendants of Fi till we get a node
            //          those closed itemset is minimal superset of closed itemset of N, that node becomes the child of N.
            L.AddConcept(x);

            foreach (Concept parent in n.GetParents(L)) {
                if (parent.Items.IsSubSetOf(x.Items)) {
                    n.RemoveParent(parent);
                    //we don't metion what is x parent now!!!
                }
            }
            n.AddParent(x);
            bool isFind = false;
            List<int> checkedItems = new List<int>();
            Case3_1_FindChildOfNInDescendantsOfFi(n, fi, tidCount, ref isFind, checkedItems);
        }

        private void Case3_1(Concept n, Concept fi, Concept x, int i, int tidCount) {
            //Case 3.1: Ifi /\ In exists as closed itemset of a node X in L
            //If such a node X existed in L then 
            //  X is parent of N. 
            //  Child of N is among the descendants of Fi. We check all the descendants of Fi till we find a node
            //      whose closed itemset is minimal superset of closed itemset of N, that node becomes the child of N

            n.AddParent(x);
            //
            FirstNodes.UpdateIndexIfExisted(i, x.ID, fi.ID);
            if (x.ChildrenID.Count == 1) {
                //in this case, x is parent of lower node => so now n is parent of lower node
                return;
            }
            //Case3_1_FindChildOfNInDescendantsOfFi(tid, n, fi);

            foreach (Concept desFi in fi.GetChildren(L)) {
                bool isFind = false;
                List<int> checkedItems = new List<int>();
                Case3_1_FindChildOfNInDescendantsOfFi(n, desFi, tidCount, ref isFind, checkedItems);
                //Case3_1_FindChildOfNInDescendantsOfFi(n, desFi);
            }

        }

        private void Case3_1_FindChildOfNInDescendantsOfFi(Concept n, Concept currentNode, int tidCount, ref bool isFind, List<int> checkedItem) {
            if (isFind) return;
            if (checkedItem.Contains(currentNode.ID)) {
                checkedItem = checkedItem.UnionWith(currentNode.ChildrenID);
                return;
            }
            foreach (int childID in currentNode.GetChildrentID()) {
                if (childID == n.ID) { continue; }
                if (checkedItem.Contains(childID)) {
                    checkedItem = checkedItem.UnionWith(L.Concepts[childID].ChildrenID);
                    continue;
                }
                Concept child = L.Concepts[childID];
                if (child.Items.IsSuperSetOf(n.Items)) {
                    n.AddChild(child);
                    checkedItem.AddUnique(childID);
                    checkedItem = checkedItem.UnionWith(child.ChildrenID);
                    if (tidCount == 1) {
                        isFind = true;
                        return;
                    }
                    //fore
                } else {
                    Case3_1_FindChildOfNInDescendantsOfFi(n, child, tidCount, ref isFind, checkedItem);
                }
            }
        }


        #endregion

        #region Case 2
        private void Case2(Concept n, Concept fi, int i, ref bool isAdded) {
            if (!isAdded) {
                L.AddConcept(n);
                isAdded = true;
            }

            //Fi is the child of N and First Node Fi corresponding to i in In is set to N.
            n.AddChild(fi);
            FirstNodes.UpdateIndexIfExisted(i, n.ID, fi.ID);

            List<int> checkedConceptIds = new List<int>();
            Case2_FindParentOfNInAncestorsFi(n, fi, checkedConceptIds);
        }

        private void Case2_FindParentOfNInAncestorsFi(Concept n, Concept fi, List<int> checkedConceptIds) {
            foreach (int parentID in fi.GetParentID()) {

                if (n.ID == parentID) { continue; }
                if (checkedConceptIds.Contains(parentID)) {
                    checkedConceptIds = checkedConceptIds.UnionWith(L.Concepts[parentID].ParentID);
                    continue;
                }
                Concept parent = L.Concepts[parentID];
                if (parent.Items.IsSubSetOf(n.Items)) {
                    bool nochildOfParentIsSuperSet = true;
                    foreach (int childOfParentID in parent.GetParentID()) {
                        if (n.ID == childOfParentID) { continue; }
                        if (checkedConceptIds.Contains(childOfParentID)) {
                            checkedConceptIds = checkedConceptIds.UnionWith(L.Concepts[childOfParentID].ParentID);
                            continue;
                        }
                        Concept childOfParent = L.Concepts[childOfParentID];
                        if (childOfParent.Items.IsSubSetOf(n.Items)) {
                            nochildOfParentIsSuperSet = false;

                            break;
                        } else
                            if (childOfParent.Items.IsSuperSetOf(n.Items)) {
                                childOfParent.RemoveParent(parent);
                                childOfParent.AddParent(n);
                                n.AddParent(parent);
                                checkedConceptIds.AddUnique(parent.ID);
                                checkedConceptIds.AddUnique(childOfParent.ID);
                                checkedConceptIds.Add(parent.ID);
                            }
                    }

                    if (nochildOfParentIsSuperSet) {
                        //=> child is subset of N
                        n.AddParent(parent);
                        checkedConceptIds.AddUnique(parent.ID);
                        checkedConceptIds = checkedConceptIds.UnionWith(parent.ParentID);
                    } else {
                        Case2_FindParentOfNInAncestorsFi(n, parent, checkedConceptIds);
                        //Case3_2_2_FindChildAndParentOfXInAncestorFi(n, parent, checkedConceptIds);
                    }
                }

            }
        }
        #endregion

        #region Case 1
        private void Case1(Concept n, Concept fi, ref bool isAdded, int tidCount) {
            //find child and parents of N among the descendants of fi

            //child of N is among the descendants of Fi. Parent(s) of N is either the node Fi itself or some of
            //Fi's descendant(s).

            //If closed itemsets of any of the child node X of Fi is superset of In then {
            //  Fi is the parent of N 
            //  X is the child node of N
            //}
            //List<Concept> children = fi.GetChildren(L);
            if (!isAdded) {
                L.AddConcept(n);
                isAdded = true;
            }
            foreach (int xID in fi.GetChildrentID()) {
                if (xID == n.ID) { continue; }

                Concept x = L.Concepts[xID];
                if (x.Items.IsSuperSetOf(n.Items)) {
                    n.AddParent(fi);
                    //TODO: update tids for ancestors fi
                    //n.AddChild(x);
                    x.RemoveParent(fi);
                    x.AddParent(n);
                    return;
                }
            }
            List<int> checkedConceptIds = new List<int>();
            List<int> notParentIds = new List<int>();
            List<int> notChildIds = new List<int>();
            bool isFind = false;
            Case1_FindParentOfNInDescendantsFi(n, fi, checkedConceptIds, notParentIds, notChildIds, tidCount, ref isFind);
        }

        private void Case1_FindParentOfNInDescendantsFi(Concept n, Concept currentNode, List<int> checkedConceptIds, List<int> notParentIds, List<int> notChildIds, int tidCount, ref bool isFind) {
            if (isFind || checkedConceptIds.Contains(currentNode.ID)) { return; }
            foreach (int childID in currentNode.GetChildrentID()) {
                if (checkedConceptIds.Contains(childID) || n.ID == childID) { continue; }

                Concept child = L.Concepts[childID];
                bool isInNotParent = notParentIds.Contains(childID);
                if (isInNotParent) {
                    notParentIds = notParentIds.UnionWith(child.ParentID);
                }

                bool isSubSet = child.Items.IsSubSetOf(n.Items);
                if (!isInNotParent && isSubSet) {
                    #region Check is parent

                    bool noChildOfChildIsSubSet = true;
                    bool needLoop = true;
                    foreach (int childOfChildID in child.GetChildrentID()) {
                        if (n.ID == childOfChildID) { continue; }
                        Concept childOfChild = L.Concepts[childOfChildID];
                        if (notParentIds.Contains(childOfChildID)) {
                            notParentIds = notParentIds.UnionWith(childOfChild.ParentID);
                            continue;
                        }

                        if (childOfChild.Items.IsSubSetOf(n.Items)) {
                            noChildOfChildIsSubSet = false;

                            notParentIds.AddUnique(childID);

                            break;
                        } else {
                            bool isInNotChild1 = notChildIds.Contains(childOfChildID);
                            if (isInNotChild1) {
                                notChildIds = notChildIds.UnionWith(childOfChild.ParentID);
                            }
                            if (!isInNotChild1 && childOfChild.Items.IsSuperSetOf(n.Items)) {
                                //remove connection between child and childOfChild
                                child.RemoveChild(childOfChild);
                                //child.AddChild(n);
                                n.AddChild(childOfChild);
                                //n found child => didn't need to loop to child of child;
                                needLoop = false;

                                //break;
                                checkedConceptIds.AddUnique(childOfChild.ID);
                                checkedConceptIds.AddUnique(childID);
                            }
                        }

                    }
                    if (noChildOfChildIsSubSet) {
                        //=> child is parent of N
                        child.AddChild(n);


                        notChildIds = notChildIds.UnionWith(child.ParentID);
                        notChildIds.AddUnique(childID);

                        notParentIds = notParentIds.UnionWith(child.ParentID);
                        notParentIds.AddUnique(childID);

                        checkedConceptIds.AddUnique(child.ID);
                    }
                    if (needLoop) {
                        Case1_FindParentOfNInDescendantsFi(n, child, checkedConceptIds, notParentIds, notChildIds, tidCount, ref isFind);
                    }
                    #endregion
                }
                bool isSuperSet = child.Items.IsSuperSetOf(n.Items);
                bool isInNotChild = notChildIds.Contains(childID);
                if (isInNotChild) {
                    notChildIds = notChildIds.UnionWith(child.ChildrenID);
                }
                if (!isInNotChild && child.Items.IsSuperSetOf(n.Items)) {

                    n.AddChild(child);
                    notChildIds = notChildIds.UnionWith(child.ChildrenID);
                    notChildIds.AddUnique(childID);

                    notParentIds = notParentIds.UnionWith(child.ChildrenID);
                    notParentIds.AddUnique(childID);
                    checkedConceptIds.AddUnique(child.ID);
                    foreach (int parentOfChildID in child.GetParentID()) {
                        if (n.ID == parentOfChildID) { continue; }
                        Concept parentOfChild = L.Concepts[parentOfChildID];
                        bool isNotInParent1 = notParentIds.Contains(parentOfChildID);
                        if (isNotInParent1) {
                            notParentIds = notParentIds.UnionWith(parentOfChild.ChildrenID);
                        }
                        if (!isNotInParent1 && parentOfChild.Items.IsSubSetOf(n.Items)) {
                            parentOfChild.RemoveChild(child);
                            parentOfChild.AddChild(n);
                            n.AddChild(child);
                            checkedConceptIds.AddUnique(child.ID);
                            checkedConceptIds.AddUnique(parentOfChild.ID);
                        }
                    }
                    if (tidCount == 1) { isFind = true; return; }
                }
                if (!isSuperSet && !isSubSet) {
                    //truong hop cua ab ne
                    Concept newNode = new Concept();
                    newNode.Items = n.Items.IntersectWith(child.Items);

                    Concept existedNode = ItemSetIsExistedInLattice(newNode.Items);
                    if (newNode.Items.Count > 0 && existedNode == null) {
                        AddTransaction(n.Tids.UnionWith(child.Tids), newNode.Items);
                    } else if (existedNode != null) {
                        n.AddParent(existedNode);
                        checkedConceptIds.AddUnique(existedNode.ID);
                    }

                }
                // Case1_FindParentOfNInDescendantsFi(n, child, checkedConceptIds, notParentIds, notChildIds, tidCount, ref isFind);
            }
        }
        #endregion

        internal Concept ItemSetIsExistedInLattice(List<int> itemSet) {
            foreach (int itemID in itemSet) {
                if (FirstNodes.Indexs.ContainsKey(itemID)) {

                    int conceptID = FirstNodes.Indexs[itemID];
                    if (L.Concepts.ContainsKey(conceptID)) {
                        Concept curConcept = L.Concepts[conceptID];
                        if (curConcept.Items.IsEqual(itemSet)) {
                            return L.Concepts[conceptID];

                        }
                    }
                    int id = -1;
                    FindItemInDescendants(L.Concepts[conceptID], itemSet, ref id);
                    if (id != -1 && L.Concepts.ContainsKey(id)) {
                        return L.Concepts[id];
                    }
                }
            }
            return null;
        }

        private void FindItemInDescendants(Concept curConcept, List<int> itemSet, ref int id) {
            if (id != -1) {
                return;
            }

            //int curIntersectCount = curConcept.Items.IntersectWith(itemSet).Length();

            foreach (Concept child in curConcept.GetChildren(L)) {
                if (child.Items.IsEqual(itemSet)) {
                    id = child.ID;
                    return;
                } else if (child.Items.IsSubSetOf(itemSet)) {
                    FindItemInDescendants(child, itemSet, ref id);
                    //int childIntersectCount = curConcept.Items.IntersectWith(itemSet).Length();
                    //if (childInter

                }
            }

        }


    }
}
